package 开始的剑指offer8月.动态规划;
// https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
public class 剑指Offer10I斐波那契数列0820 {
    class Solution {
        public int fib(int n) {
            // if(n==0){
            //     return 0;
            // }
            // else  if(n<2){
            //     return 1;
            // }
            // int sum=0;
            // sum=fib(n-1)+fib(n-2);
            // return sum;

            // int ans[] = new int[101];
            // ans[0] = 0;
            // ans[1] = 1;
            // for(int i=2;i<=n;i++){
            //     ans[i] = ans[i-1] + ans[i-2];
            //     ans[i] = ans[i]%1000000007;
            // }
            // return ans[n];

            // if(n==0){
            //     return 0;
            // }
            // else  if(n<2){
            //     return 1;
            // }
            // int sum=0;
            // int one=1;
            // int two=0;
            // for(int i=2;i<=n;i++)
            // {
            //     sum=(one+two)%(1000000007);
            //     two=one;
            //     one=sum;
            // }
            // return sum;



            int a = 0, b = 1, sum;
            for(int i = 0; i < n; i++){
                sum = (a + b) % 1000000007;
                a = b;
                b = sum;
            }
            return a;



        }
    }
}
